package com.wp.InterviewAlgorithm.lesson1;

/**
 * Created by 王萍 on 2017/9/18 0018.
 */

import com.wp.utils.LinkedListUtil.Node;

import static com.wp.utils.LinkedListUtil.printNode;

/**
 * 给定两个单向链表，计算两个链表的第一个公共节点，若没有公共节点，返回空。
 */
public class 单链表公共节点 {

    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(4);
        Node node3 = new Node(5);
        Node node4 = new Node(5);
        Node node5 = new Node(7);
        Node node6 = new Node(9);
        Node node7 = new Node(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        Node first = new Node(100);
        Node second = new Node(200);
        first.next = node6;
        node6.next = node5;
        second.next = node7;

        node5.next = node1;
        node7.next = node1;

        printNode(first);
        printNode(second);
        Node commonNode = getCommonNode(first, second);
        System.out.println("公共节点的值为：" + commonNode.value);
    }

    private static Node getCommonNode(Node first, Node second) {
        int firstListLength = calcListLength(first);
        int secondListLength = calcListLength(second);
        if (secondListLength > firstListLength) {
            Node tmp = first;
            first = second;
            second = tmp;

            int tmpInt = firstListLength;
            firstListLength = secondListLength;
            secondListLength = tmpInt;
        }
        for (int i = 0; i < firstListLength - secondListLength; i++) {
            first = first.next;
        }
        while (first != null) {
            if (first == second) return first;
            first = first.next;
            second = second.next;
        }
        return null;
    }


    private static int calcListLength(Node node) {

        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}
